package leetcode_161_180;

public class findPeakElement_162 {
    /**
     * 寻找整数数组 nums 的峰值元素并返回其索引。
     * 数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
     * 可以假设 nums[-1] = nums[n] = -∞ 。
     * 时间复杂度必须为 O(log n)
     */
    public int findPeakElement(int[] nums) {
        /**
         * 想不出来思路
         * O(log n)大概率使用二分查找，但是没有思路
         *
         * 高解思路
         * 根据题目前提，即无重复数字，及左右视为负无穷
         * 1，对于任意数组而言，一定存在峰值（一定有解）；
         *  由于1，如果当前位置大于其左边界或者右边界，那么在当前位置的右边或左边必然存在峰值。
         * 2，二分不会错过峰值。
         * 所有每次只需要选择一定含有峰值的范围即可
         * 0ms
         */
        int len=nums.length;
        int left=0,right=len-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]>nums[mid+1])  //放弃右半部分
                right=mid;
            else                    //放弃左半部分以为中点坐标
                left=mid+1;
        }
        return left;
    }
}
